/**
 * Copyright (C) 2002 Michael Green <mtgreen@cs.ucsd.edu>
 * 
 * Copyright (C) 2002 Paul Kube <kube@cs.ucsd.edu>
 * 
 * Copyright (C) 2005 Owen Astrachan <ola@cs.duke.edu>
 * 
 * Copyright (C) 2011 Hoa Long Tam <hoalong.tam@berkeley.edu> and Armin Samii
 * <samii@berkeley.edu>
 * 
 * This file is part of CS Boggle.
 * 
 * CS Boggle is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 * 
 * CS Boggle is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
 * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along with
 * CS boggle. If not, see <http://www.gnu.org/licenses/>.
 */

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class WordOnBoardFinder {
	private BoggleBoard currBoard;
	
  /**
   * Return a list of cells on the given board such that the i-th element of the
   * list corresponds to the i-th character of the string as found on the board.
   * Returns an empty list if the word cannot be found on the board.
   * 
   * @param board
   *          is searched for the given word
   * @param word
   *          is being searched for on the board
   * @return list of cells on the supplied board that correspond to the word, an
   *         empty list should be returned if the word cannot be found on the
   *         board
   */
  public List<BoardCell> cellsForWord(BoggleBoard board, String word) {
	currBoard = board;
    List<BoardCell> list = new ArrayList<BoardCell>();
    if(word.isEmpty()){
    	return list;
    }
    String currLetter = getCurrLetter(word);
    for (int r = 0; r < board.size(); r++) {
      for (int c = 0; c < board.size(); c++) {
        if(board.getFace(r, c).equals(currLetter)){
        	list = checkPoint(new BoardCell(r,c), board, word.substring(currLetter.length()));
        	if(!list.isEmpty()){
        		return list;
        	}
        }
      }
    }
    return list;
  }  

  /**
   * Returns the first letter of the word in question. Considers QU to be a single letter.
   * @param word	the word in question
   * @return 		first letter of the string word
   */
  private static String getCurrLetter(String word){
	String currLetter = word.substring(0,1);
	if(currLetter.equals("q") && word.substring(1, 2).equals("u")){
		  currLetter = "qu";
	}
	return currLetter;
  }
  
  /**
   * Tests the private method getCurrLetter's to functions:
   * * Returning the first letter of a normal word (not starting with q)
   * * Returning "qu" for a word that starts with qu
   * @return	true if both tests pass.
   */
  private static boolean testGetCurrLetter(){
	  String word = "whack";
	  String currLetter = WordOnBoardFinder.getCurrLetter(word);
	  if(!currLetter.equals("w")){
		  return false;
	  }
	  word = "quake";
	  currLetter = WordOnBoardFinder.getCurrLetter(word);
	  if(!currLetter.equals("qu")){
		  return false;
	  }
	  return true;
  }
  
  /**
   * Creates a word tree and checks if there is a path available. If none is found, it returns an empty List.
   * @param start The cell to begin the tree at.
   * @param board The boggle game board variable.
   * @param word  The word the tree must search for
   * @return	  A list of BoardCell objects that represent the path of the String 'word' located on the BoggleBoard 'board'. 
   * 			  Returns an empty list if no path is found.
   */
  private ArrayList<BoardCell> checkPoint(BoardCell start, BoggleBoard board, String word){
	  WordTree cellTree = new WordTree(start, board, word);
	  ArrayList<BoardCell> path = cellTree.convertMyPath(); 
	  return path;
  }

  
 /**
  * Inner tree class that handles all of the actual word finding. 
  * Essentially, WordTree will build a tree that contains all the possible paths to a word.
  * @author Austen
  *
  */
  private static class WordTree{
	  public WordTreeNode myRoot;
	  private String myWord;
	  private BoggleBoard myBoard;
	  private boolean isValid = false;
	  private ArrayList<WordTreeNode> myPath = new ArrayList<WordTreeNode>();
	  
	  /**
	   * Initializes instance variables and calls BuildTree to construct the paths	   * 
	   * @param start	The cell to begin the search at. This should be the cell containing the first letter of the word.
	   * @param board	A reference to the BoggleBoard where the search should take place
	   * @param word	The word to search for. This should be truncated, including everything but the first letter already referenced by 'start'.
	   */	  	   
	  public WordTree(BoardCell start, BoggleBoard board, String word){
		  myRoot = new WordTreeNode(start);
		  myBoard = board;
		  myWord = word;
		  buildTree(myRoot,myWord, new ArrayList<WordTreeNode>());
		  if(myPath.size()-1==word.length()){
			  isValid = true;
		  }
	  }

	  /**
	   * Simply prints the tree out to the console. Used only for debugging.
	   * Prints in preorder.
	   */
	  private void print() {
		if(myRoot != null){
			printHelper("",myRoot);
		}
	  }
	  
	  private void printHelper(String indents, WordTreeNode currNode){
		  int row = currNode.myItem.row;
		  int col = currNode.myItem.col;
		  System.out.println(indents+"("+row+","+col+") "+currNode);
		  for(int i=0;i<currNode.myChildren.size();i++){			  
			  printHelper(indents+"    ",currNode.myChildren.get(i));
		  }
	  }
	  
	  /**
	   * Builds a tree that contains all the possible pathways to a word, starting from the cell contained in t.
	   * Also returns the most complete path of nodes to form a word.
	   * If this path is equal to the size of myWord, it can be assumed that the path is complete and the word is on the board.
	   * @param t		Should initially be called with myRoot. buildTree will search around this node for the next letter in word
	   * @param word	The word to build a path for.
	   * @param soFar	Used to keep a trail of past nodes. Should initially be empty.
	   * @return 		Most complete path of nodes to myWord
	   */
	  private void buildTree(WordTreeNode t, String word, ArrayList<WordTreeNode> soFar){
		  soFar.add(t);
		  if(!word.isEmpty()){
			  String currLetter = getCurrLetter(word);
			  ArrayList<WordTreeNode> matching = searchAround(t.myItem,currLetter);
			  /**
			   * Checks current node trail against further matched nodes to eliminate duplicates			   * 
			   */
			  for(Iterator<WordTreeNode> m = matching.iterator();m.hasNext();){
				  WordTreeNode currNode = m.next();
				  if(!soFar.contains(currNode)){
					  t.myChildren.add(currNode);
				  }
			  }
			  
			  for(Iterator i = t.myChildren.iterator();i.hasNext();){
				  WordTreeNode child = (WordTreeNode)i.next();
				  ArrayList<WordTreeNode> childSoFar = new ArrayList<WordTreeNode>();
				  childSoFar.addAll(soFar);
				  buildTree(child,word.substring(currLetter.length()),childSoFar);
			  }	
		  }else{
			  myPath = soFar;
		  }		  	  
	  }
	  
	  /**
	   * Converts this tree's myPath list to a list of BoardCells.
	   * @return A list of BoardCells symbolizing this tree's myPath list
	   */
	  public ArrayList<BoardCell> convertMyPath(){
		  ArrayList<BoardCell> convertedList = new ArrayList<BoardCell>();
		  for(Iterator<WordTreeNode> i=myPath.iterator();i.hasNext();){
			convertedList.add(i.next().myItem);  
		  }
		  return convertedList;
	  }
	  
	  /**
	   * Searches around a given BoardCell for any matches of a given letter.
	   * @param b			The BoardCell to search around.
	   * @param currLetter	The letter to search for.
	   * @return			An ArrayList of all matching BoardCells.
	   */
	  private ArrayList<WordTreeNode> searchAround(BoardCell b, String currLetter){
		  ArrayList<WordTreeNode> matching = new ArrayList<WordTreeNode>();
		  int r = b.row;
		  int c = b.col;
		  int startR = r;
          int startC = c;
          if(r!=0){
              startR = r-1;
          }       
          if(c!=0){
              startC = c-1;
          }       
          
          for(int rr = startR ; rr<=r+1 && rr<myBoard.size() ; rr++){
              for(int cc = startC ; cc<=c+1 && cc<myBoard.size() ; cc++){
                  if(myBoard.getFace(rr,cc).equals(currLetter)){
                	  WordTreeNode newNode = new WordTreeNode(new BoardCell(rr,cc));
                	  matching.add(newNode);
                  }                       
              }
          }
          return matching;
	  }
	  
	  /**
	   * Inner node class. Represents a single node in the tree.
	   * @author Austen
	   *
	   */
	  public class WordTreeNode{
		  public BoardCell myItem;
		  public ArrayList<WordTreeNode> myChildren;
		  /**
		   * Creates a new node with item as its contents.
		   * @param item	The contents of the new node.
		   */
		  public WordTreeNode(BoardCell item){
			  myItem = item;
			  myChildren = new ArrayList<WordTreeNode>();
		  }
		  
		  /**
		   * @return the String value represented by BoardCell on the BoggleBoard myBoard.
		   */
		  public String toString(){
			  int row = myItem.row;
			  int col = myItem.col;
			  return myBoard.getFace(row,col);
		  }
		  
		  /**
		   * Compares the contents of two nodes
		   * @param w The node to compare with.
		   * @returns True if the contents of both nodes are equal.
		   */
		  public boolean equals(Object w){
			  WordTreeNode subject = (WordTreeNode) w;
			  return myItem.equals(subject.myItem);
		  }
		  
	  }
  }
  
  /**
   * Tests WordTree's buildTree() (via the constructor) and convertMyPath() methods.
   * @return True if test passes.
   */
  private static boolean testBuildTree(){
	  BoardMaker myMaker = new BoardMaker();
	  String[] boardContents = { "nenjd", "eiahh", "tuitl", "pnrrr", "pnren" };
	  BoggleBoard board = myMaker.makeBoard(boardContents); 
	  WordOnBoardFinder.WordTree treeTest = new WordOnBoardFinder.WordTree(new BoardCell(4,0),board,"nren");
	  ArrayList<BoardCell> correct = new ArrayList<BoardCell>();
	  correct.add(new BoardCell(4,0));
	  correct.add(new BoardCell(4,1));
	  correct.add(new BoardCell(4,2));
	  correct.add(new BoardCell(4,3));
	  correct.add(new BoardCell(4,4));
	  if(!correct.equals(treeTest.convertMyPath())){
		  return false;
	  }else{
		  return true;
	  }
  }
  
  /**
   * Tests the WordTree's private helper method searchAround(). 
   * @return True if test passes.	
   */
 private static boolean testSearchAround(){
	  BoardMaker myMaker = new BoardMaker();
	  String[] boardContents = { "nenjd", "eiahh", "tiitl", "inrrr", "pnren" };
	  BoggleBoard board = myMaker.makeBoard(boardContents); 
	  WordOnBoardFinder.WordTree treeTest = new WordOnBoardFinder.WordTree(new BoardCell(2,0),board,"ie");
	  treeTest.myPath = treeTest.searchAround(treeTest.myRoot.myItem, "i");
	  ArrayList<BoardCell> result  = treeTest.convertMyPath();
	  ArrayList<BoardCell> correct = new ArrayList<BoardCell>();
	  correct.add(new BoardCell(1,1));
	  correct.add(new BoardCell(2,1));
	  correct.add(new BoardCell(3,0));
	  if(!result.equals(correct)){
		  return false;
	  }else{
		  return true;
	  }
  }

  /**
	 * Tests private functions and returns and integer based on which one failed first.
	 * @return	0 if all tests passed, or a number depending on which test failed first.
	 */
	public static int testPrivateFunctions(){
		if(!testGetCurrLetter()){
			return 1;
		}
		
		if(!testBuildTree()){
			return 2;
		}
		
		if(!testSearchAround()){
			return 3;
		}		
		
		return 0;
	}
	
}
